package search;

import java.util.Arrays;

public class FibonacciSearch {
    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(fibSearch(arr, 0));

    }

    private static int fibSearch(int[] arr, int value) {
        // 需要排列的数组扩容
        int k = 2;
        while (arr.length > FibonacciSeq.fibonacci(k)) {
            k++;
        }
        int[] temp = Arrays.copyOf(arr, FibonacciSeq.fibonacci(k));
        // 填充arr最大值
        for (int i = arr.length; i < FibonacciSeq.fibonacci(k); i++) {
            temp[i] = temp[arr.length - 1];
        }
        return f(temp, 0, temp.length - 1, value, k, arr.length);
    }

    /**
     * 从 temp 数组中找黄金分割点，
     * 黄金分隔点即是斐波那契数组的前一索引位置的数字
     * 斐波那契的特点：f[k] = f[k-1] + f[k-2] ===》 f[k]-1 = f[k-1]-1 + f[k-2]-1 +1
     * 黄金分割点的值为 f[k-1] -1,正常黄金分割点的值应该是f[k-1],但这里代表的是数组的索引，从0开始，故这里需要对其进行-1操作
     *                         left是作为获取黄金分隔点的基准值
     */
    private static int f(int[] temp, int left, int right, int value, int k, int arrLen) {
        // 数组长度从0开始，需要减一
        int mid = left + FibonacciSeq.fibonacci(k - 1) - 1;
        if (left <= right) {
            /**  key < array[low]：小于最小值
             *  key > array[high]：大于最大值
             *  low > high：遍历整个数组均未找到元素，退出
             **/

            if (temp[mid] > value) {
                k -= 1;
                return f(temp, left, mid - 1, value, k, arrLen);
            } else if (temp[mid] < value) {
                k -= 2;
                return f(temp, mid + 1, right, value, k, arrLen);
            } else {
                // 我们黄金分割的是temp数组，可能会找到"填充的元素"
                //middle的值已经大于high,进入扩展数组的填充部分,即最后一个数就是要查找的数。
                if (mid <= arrLen - 1) {
                    return mid + 1;
                } else {
                    return arrLen;
                }
            }
        }
        return -1;
    }
}
